package com.sheng.leetcode.year2022.month06.day14;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/06/14
 *
 * 498. 对角线遍历
 *
 * 给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。
 *
 * 示例 1：
 *
 * 输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
 * 输出：[1,2,4,7,5,3,6,8,9]
 * 示例 2：
 *
 * 输入：mat = [[1,2],[3,4]]
 * 输出：[1,2,3,4]
 *
 * 提示：
 *
 * m == mat.length
 * n == mat[i].length
 * 1 <= m, n <= 104
 * 1 <= m * n <= 104
 * -105 <= mat[i][j] <= 105
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/diagonal-traverse
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0498 {

    @Test
    public void test01(){
//        int[][] mat = {{1,2,3},{4,5,6},{7,8,9}};
//        int[][] mat = {{1,2},{3,4}};
//        int[][] mat = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
        int[][] mat = {{1,2,3,4},{5,6,7,8}};
        int[] diagonalOrder = new Solution().findDiagonalOrder(mat);
        for (int i = 0; i < diagonalOrder.length; i++) {
            System.out.println(diagonalOrder[i]);
        }
    }

}
class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        //奇数遍历右上方向，偶数遍历左下方向，通过遍历的次数判断是否到达边界
        int m = mat.length - 1;
        int n = mat[0].length - 1;
        int[] ints = new int[mat.length * mat[0].length];
        int i = 0, j = 0;
        int k = 0;
        while (i <= m && j<= n) {
            //将遍历的值存入新数组
            ints[k] = mat[i][j];
            k++;
            //到达最后点
            if (i == m && j == n){
                return ints;
            }
            if ((i + j) % 2 == 0) {
                //奇数层遍历，方向右上
                //判断是否到达这一层遍历的边界，到达右上边界有两种判断，一种为抵达上边界，一种为抵达右边界
                if (j == n) {
                    //抵达右边界
                    i++;
                } else if (i == 0) {
                    //抵达上边界
                    j++;
                } else {
                    //往右上继续走
                    i--;
                    j++;
                }
            } else {
                //偶数层遍历，方向左下
                if (i == m) {
                    //抵达下边界
                    j++;
                } else if (j == 0) {
                    //抵达左边界
                    i++;
                } else {
                    //往左下继续走
                    i++;
                    j--;
                }
            }
        }
        return ints;
    }
}
